using System;
using System.Collections.Generic;
using System.Text;
using Imagination.Collisions;
using Microsoft.Xna.Framework;


namespace Imagination.Partitioning
{
    /// <summary>
    /// AxisPartitioner tracks Things in one dimension along a specific axis. (currently this is hardcoded to the X axis)
    /// If two objects don't collide in one dimension, they also aren't colliding in three dimensions. AxisPartitioner
    /// optimizes for one dimension to narrow down the list of potential collisions more efficiently than could be performed
    /// in 3D.
    /// </summary>
    public class AxisPartitioner : Partitioner, IContainThings
    {
        private enum IntervalMarkerType
        {
            Start,
            End
        }

        /// <summary>
        /// IntervalMarker
        /// </summary>
        private class IntervalMarker
        {
            public Thing Owner;
            public IntervalMarkerType MarkerType;
            public float Coordinate;
            public LinkedListNode<IntervalMarker> Node;

            public IntervalMarker(Thing owner, IntervalMarkerType markerType, float coordinate)
            {
                this.Owner = owner;
                this.MarkerType = markerType;
                this.Coordinate = coordinate;
                this.Node = null;
            }

            public void Sort()
            {
                if (Node == null || Node.List == null) 
                    throw new ImaginationException("The specified marker is not part of the linked list.");

                LinkedList<IntervalMarker> markers = Node.List;

                if (Node.Previous != null &&
                    Node.Previous.Value.Coordinate > Coordinate)
                {
                    bool done = false;
                    LinkedListNode<IntervalMarker> searchNode = Node.Previous;
                    while (!done)
                    {
                        if (searchNode == null)
                        {
                            //  reached beginning of list; add node to front of list
                            markers.Remove(Node);
                            markers.AddFirst(Node);
                            break;
                        }
                        if (searchNode.Value.Coordinate <= Coordinate)
                        {
                            markers.Remove(Node);
                            markers.AddAfter(searchNode, Node);
                            break;
                        }
                        searchNode = searchNode.Previous;
                    }

                }
                else if (Node.Next != null &&
                    Node.Next.Value.Coordinate < Coordinate)
                {
                    bool done = false;
                    LinkedListNode<IntervalMarker> searchNode = Node.Next;
                    while (!done)
                    {
                        if (searchNode == null)
                        {
                            //  reached end of list; add node to end of list
                            markers.Remove(Node);
                            markers.AddLast(Node);
                            break;
                        }
                        if (searchNode.Value.Coordinate > Coordinate)
                        {
                            markers.Remove(Node);
                            markers.AddBefore(searchNode, Node);
                            break;
                        }
                        searchNode = searchNode.Next;
                    }

                }
            }
        }

        /// <summary>
        /// IntervalMarkerPair
        /// </summary>
        private class ThingInterval
        {
            public Thing Owner;
            public IntervalMarker Lower;
            public IntervalMarker Upper;

            public ThingInterval(Thing owner)
            {
                this.Owner = owner;

                float x = Owner.Position.X;
                float r = Owner.Boundary.Radius;

                this.Lower = new IntervalMarker(owner, IntervalMarkerType.Start, x - r);
                this.Upper = new IntervalMarker(owner, IntervalMarkerType.End, x + r);
            }

            public void Update()
            {
                float x = Owner.Position.X;
                float r = Owner.Boundary.Radius;

                this.Lower.Coordinate = x - r;
                this.Upper.Coordinate = x + r;

                this.Lower.Sort();
                this.Upper.Sort();
            }
        }

        private Dictionary<Thing, ThingInterval> intervals;
        private LinkedList<IntervalMarker> markers;
        private Zone zone;

        public AxisPartitioner(Zone zone) : base()
        {
            //  HACK: hard-coded initial capacity for dictionary; should probably be configurable
            intervals = new Dictionary<Thing, ThingInterval>(250);
            markers = new LinkedList<IntervalMarker>();
            this.zone = zone;
        }

        public void ThingMoved(Thing thing)
        {
            intervals[thing].Update();
        }

        public override void CheckCollisions(CollisionDetector detector)
        {
            List<Thing> activeThings = new List<Thing>();
			Thing thing1;
			Collision collision;

            if (markers.Count == 0) return;

			LinkedListNode<IntervalMarker> location = markers.First;
			while (location != markers.Last)
			{
				if (location.Value.MarkerType == IntervalMarkerType.Start)
				{
					thing1 = location.Value.Owner;
					foreach(Thing thing2 in activeThings)
					{
                        //  make sure at least one object calls this zone home
                        if (thing1.Zone != this.zone && thing2.Zone != this.zone)
                            continue;

						collision = detector.DetectCollision(thing1, thing2);
						if (collision != null)
						{
							thing1.RespondToCollision(collision);
							thing2.RespondToCollision(collision);
						}
					}
					activeThings.Add(thing1);
				}
				else
				{
					activeThings.Remove(location.Value.Owner);
				}
				location = location.Next;
			}
        }

        public override void CheckPartitioning(Thing thing)
        {
            throw new Exception("The method or operation is not implemented.");
        }

        public override List<Zone> GetVisibleZones(Imagination.Display.Camera camera)
        {
            throw new ImaginationException("GetVisibleZones is not supported. AxisPartitioner does not contain Zones.");
        }

        public override void Clear()
        {
            intervals.Clear();
            markers.Clear();
        }

        private LinkedListNode<IntervalMarker> AddMarker(IntervalMarker marker)
        {
            LinkedListNode<IntervalMarker> newNode = new LinkedListNode<IntervalMarker>(marker);
            marker.Node = newNode;

            if (markers.Count == 0)
            {
                markers.AddFirst(newNode);
                return newNode;
            }

            bool done = false;
            LinkedListNode<IntervalMarker> node;
            node = markers.First;
            while (!done)
            {
                if (marker.Coordinate <= node.Value.Coordinate)
                {
                    //  we found a marker at least as big as this one... time to pop it into the list
                    markers.AddBefore(node, newNode);
                    done = true;
                }
                else if (node.Next == null)
                {
                    // walked through the whole list; add it to the end
                    markers.AddLast(newNode);
                    done = true;
                }
                else
                {
                    node = node.Next;
                }
            }
            return newNode;
        }


        #region IContainThings Members

        public void AddThing(Thing thing)
        {
            //if (zone.Contains(thing) != ContainmentType.Disjoint)
            //{
                ThingInterval interval = new ThingInterval(thing);

                AddMarker(interval.Upper);
                AddMarker(interval.Lower);

                intervals.Add(thing, interval);
            //}
        }

        public void RemoveThing(Thing thing)
        {
            //if(intervals.ContainsKey(thing))
            //{
                ThingInterval interval = intervals[thing];
                intervals.Remove(thing);
                markers.Remove(interval.Lower);
                markers.Remove(interval.Upper);
            //}
        }

        public void ClearThings()
        {
            Clear();
        }

        public IEnumerable<Thing> EnumerateThings()
        {
            foreach (Thing thing in intervals.Keys)
            {
                yield return thing;
            }
        }

        #endregion
    }
}
